\documentclass[a4paper,10pt]{article}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage{listings}

%opening
\title{}
\author{}

\lstset{language=C}

\begin{document}

\maketitle


\section{Introduction}

We will begin introducing the functionality of TopologicalLearnerAPI by looking at the class ``Graph'' and the class ``GraphDatabase''.
The ``Graph''-class represents an indoor topological map and is internally a boost graph object (an adjacency\_list). Each vertex
has a unique number associated to it which represents the semantic category of the vertex. The graphs are undirected.

We may retreive the unique ID of a semantic category (a string) and vice versa:

\begin{lstlisting}
GraphDatabase D;
int iOfficeID = D.GetVertexIDFromString("OFF");
string sOffice = D.GetStringFromVertexID(iOfficeID);
\end{lstlisting}

Basically the ``GraphDatabase'' class represents a set of graphs, i.e $\mathcal{D}=\{G_1, ..., G_n\}$ where each $G_i=(V_i, E_i)$ is a undirected graph.

\subsection{Loading a graph database}

We may load a ``GraphDatabase'' in two ways, either from a directory of XML-files or from a previously serialized ``GraphDatabase''-object.

The following code demonstrates how to load a ``GraphDatabase'' from a directory of XML-files (it will recursivly search subdirectories as well):
\begin{lstlisting}
    GraphDatabase D;
    D.LoadAllGraphs("corpus/");
    cout << "Graphs loaded: " << D.GetNumGraphs() << endl;
\end{lstlisting}

We may also serialize and deserialize ``GraphDatabase'' objects themselves:
\begin{lstlisting}
    D.Save("GD.dat");
    D.Load("GD.dat");
\end{lstlisting}

We usually want to make sure that a loaded graph database from XML satisfies connectivity.
Below is a code snippet that shows how one usually loads a graph database from XML-files and ensures their connectivity
and then save the result:

\begin{lstlisting}
    D.LoadAllGraphs("corpus/");
    D.RemoveIsolatedVertices();
    D.RemoveDisconnectedGraphs();
    D.GenerateFrequentSubgraphs(0.05);
    D.Save("GD.dat");
\end{lstlisting}

\subsection{Accessing the graph database and edit operations}

We may retreive an individual graph from the GraphDatabase by specifiying its ID:

\begin{lstlisting}
    Graph G = D.GetGraph(10);
    // Get graph # 10 and save it to file (dot-format)
    GraphFunctions::SaveGraph("graph.dot", G, &D);
\end{lstlisting}

The code example below demonstrates how one can create a graph by using so called EditOperations. An EditOperation
is either a vertex addition or an edge addition. What this means is simply that, given a graph (can be empty), the edit operation
specifies either the addition of a vertex to the graph (and connecting it to some existing vertex if possible) or the addition
of an edge between two already existing vertices on the graph:

\begin{lstlisting}
    Graph G1;

    // Apply the edit operation add vertex, add an office
    int iOfficeID = D.GetVertexIDFromString("OFF");
    G1 = GraphFunctions::ApplyEditOp(G1, EditOp(true, 0, iOfficeID));

    // Add a corridor and connect it to the office
    int iCorrID = D.GetVertexIDFromString("CORR");
    G1 = GraphFunctions::ApplyEditOp(G1, EditOp(true, iOfficeID, iCorrID));
\end{lstlisting}

The EditOp and EditOpDist is defined by:

\begin{lstlisting}
typedef boost::tuple<bool, unsigned int, unsigned int> EditOp;
typedef std::map<EditOp, double > EditOpDist;
\end{lstlisting}

The first value of an EditOperation specifies if it is a vertex addition or an edge addition. The second and third components
specify the unique vertex ID of the vertices involved in the operation.
An EditOpDist is a mapping from edit operations to doubles, and this is the return structure from a Predictor (more on this below).
It simply gives a discrete probability distribution over different edit operations on a specified graph.

ApplyEditOp returns the resulting graph of performing an edit operation on a specified graph.

\subsection{Frequent subgraph generation}

After loading the graphs in a graph database, it is essential to produce a set of frequent subgraphs.
These are stored internally in the GraphDatabase object and are generated by the gSpan function.
The set of FrequentSubgraphs in a GraphDatabase are serializable.
Below is a code example on how to generate the frequent subgraphs for a given threshold. It also demonstrates
what we can do when we've generated this set, given any graph we may check which frequent subgraphs are present in the graph.
This can be used as a feature vector when doing Prediction for example:

\begin{lstlisting}
std::set< const FrequentSubgraph* > 
GraphDatabase::GetOccuringFrequentSubgraphs(const Graph& G, 
unsigned int iMinSize) const
\end{lstlisting}

Given a graph $G$, generate the frequent subgraphs and then check if they're present in the graph:

\begin{lstlisting}
D.GenerateFrequentSubgraphs(0.05);
// We only want subgraphs of at least size 2 (to avoid getting single vertex frequent subgraphs).
set< const FrequentSubgraph* > res = D.GetOccuringFrequentSubgraphs(G, 2);
\end{lstlisting}

A FrequentSubgraph is simply defined by the class:
\begin{lstlisting}
struct FrequentSubgraph
{
public:
    Graph G;
    std::vector<int> vGraphIDs;
}
\end{lstlisting}

In brief, $G$ is the frequent subgraph and vGraphIDs is a vector of IDs of all the graphs in the graph database in which this
frequent subgraph occur.

The main objects of the API are the Predictors. A Predictor is an abstract baseclass with the following essential functions:
\begin{lstlisting}
virtual EditOpDist Predict(const Graph& G) = 0;
virtual void AttachDatabase(const GraphDatabase* pD);
\end{lstlisting}

The following code example shows how it may be used to get a discrete probability distribution over edit operations:

\begin{lstlisting}
    BFPredictor BFP;
    BFP.AttachDatabase(&D);

    EditOpDist kResDist = BFP.Predict(G1);

    EditOpDist::iterator it;
    for(it = kResDist.begin(); it != kResDist.end(); it++ )
        cout << it->second << endl;
\end{lstlisting}

The example creates a brute force predictor, and prints out the probability of each edit operation.
One could easily here select the operation with the highest probability and use the ApplyEditOp function as above
to get a predicted graph. 

\section{How to generate test data and benchmark a predictor}

In this section we will examine how we can test the performance of a given predictor and a graph database.
The performance of a Predictor is measured as the number of times it manages to do a correct prediction on a given testing set.

The testing set is defined by a set of graphs, and for each of these graphs we have randomly selected a connect subgraphs.
The Predictor is then given this connected subgraphs and is asked to make a prediction. A prediction is correct
if the predicted node/edge exists in the larger graph.

Formally, let $T=\{ (G_1, g_1), (G_2, g_2), \dots , (G_n, g_n) \}$ be the testing set, where for each $i$ we have that $g_i \subset G_i$.
Let $P(g_i)=g_i'$ be the resulting graph of performing a prediction on $g_i$, then the performance of a Predictor is 
given by $\sum_i I(P(g_i) \subseteq G_i) $, where $I(X \subseteq Y) = 1$ if $X \subseteq Y$, $0$ otherwise. 

The set $T$ is represented by the class \emph{TestingSet}. We may generate it by using the function ``GenerateTestingSet'' defined below.
The class ``AlgorithmStats'' is responsible for performing the actual test upon a ``TestingSet'' object, given a ``GraphDatabase'' and a ``Predictor'' class. 

The definition of the relevant functions are given below:


\begin{lstlisting}
void TestingSet::GenerateTestingSet(vector<unsigned int> PGSizes,
 const GraphDatabase& D)
double AlgorithmStats::TestAll(TestingSet& kT,
 const Predictor* pPredictor, string sFilename)
\end{lstlisting}

The vector ``PGSizes'' above determines how many graphs we should create for each possible graph size.
The value returned by TestAll is the number of successful predictions divided by the total number of elements in the test set.
The function will save the results of the test to the specified file (where the success frequency is given as a function of the
size of the graphs $g_i$). This is so that we can see how the predictor performs on graphs of different size.


Finally below is a code example that combines all that we've discussed:


\begin{lstlisting}
    // We want to generate graphs of graph size 1-10, and 100 of each
    // thus in total 1000 different graphs.
    vector<unsigned int> sizes;
    sizes.push_back(0);
    for(int i=1; i < 11; i++)
        sizes.push_back(100);

    kTest.GenerateTestingSet(sizes, D);
    
    BFPredictor P;
    P.AttachDatabase(D);
    
    // Perform the benchmark
    AlgorithmStats stats;
    dResult = stats.TestAll(kTest, P, "BFPredictor.dat");
\end{lstlisting}

\end{document}
